package knapsackML;

import java.util.Scanner;

public class knapsackML {
    public static void main(String[] args) {
        // 读入数据的代码
        Scanner Sc = new Scanner(System.in);
        System.out.println("输入物品的数量和背包的最大容量使用空格隔开");
        // 物品的数量为N
        int N = Sc.nextInt();
        // 背包的最大容量为V
        int V = Sc.nextInt();
        // 一个长度为N的数组，第i个元素表示第i个物品的重量
        int[] v = new int[N + 1];
        // 一个长度为N的数组，第i个元素表示第i个物品的价值；
        int[] w = new int[N + 1];
        System.out.println("请输入物品的重量和价值使用空格隔开");
        for (int i = 1; i <= N; i++) {
            // 接下来有 N 行，每行有两个整数:v[i],w[i]，用空格隔开，分别表示第i件物品的体积和价值
            v[i] = Sc.nextInt();
            w[i] = Sc.nextInt();
        }

        int maxW = 0;
        int maxV = 0;
        int[] bestChoice = new int[N + 1];
        //枚举所有可能的情况 每个物品选或者不选的问题 0为不选，1为选
        for (int i = 0; i < Math.pow(2, N); i++) {
            int cw = 0;  // 当前组合的重量
            int cv = 0;  // 当前组合的价值
            for (int j = 0; j < N; j++) {
                if (((i / (int) Math.pow(2, j)) % 2) != 0) {  // 检查第j位是否为1
                    cw += v[j + 1];
                    cv += w[j + 1];
                }
            }
            //比较每一种选法的价值与最大价值进行进行交换
            if (cw <= V && cv > maxV) {
                System.out.println("第"+(i+1)+"种组合的价值"+cv);
                maxV = cv;
                maxW = cw;
                bestChoice = new int[N + 1];
                for (int j = 0; j < N; j++) {
                    if (((i / (int) Math.pow(2, j)) % 2) != 0) {   // 检查第j位是否为1
                        bestChoice[j+1] = 1;
                    }
                }
            }
        }

        System.out.print("包内的物品编号为：");
        for (int i = 1; i <= N; i++) {
            if (bestChoice[i] == 1) {
                System.out.print(i + " ");
            }
        }
        System.out.println();
        System.out.println("包内能承载的物品最大价值为：" + maxV);
    }
}